1. Field of the Invention
This invention relates to the field of one-dimensional interpolation and in particular to one-dimensional interpolation requiring fewer mathematical operations or fewer interpolator circuit elements.
2. Background of the Invention
It is well known in the art to perform one-dimensional interpolation. One-dimensional interpolation involves the weighted summation of two values, for example, as expressed by the equation I=xA+(1-x)B. In this equation A and B are the two input values to be interpolated and x is the fractional weight term. The solution of this equation requires two add/subtract operations and two multiplications.
It is known to rearrange this equation to reduce it to the following form: I=x(A-B)+B. When the basic one-dimensional interpolation equation is rearranged into this form, the solution of the interpolation requires one subtraction, one addition, and one multiplication. Thus this rearranged form requires one less multiplication. Because this rearranged form requires fewer mathematical operations, it is advantageous to design a circuit to solve the equation in this rearranged form. This advantage can be realized in the form of decreased space requirements on the semiconductor chip or in performing the interpolation more quickly using the same amount of space. However, it is desirable to further reduce the amount of space or time required to perform the interpolation.
It is also well-known in the art to provide parallel multipliers for multiplying binary numbers. A parallel multiplier is based on the observation that partial products in the multiplication process can be independently computed in parallel. For example, consider the unsigned binary integers A and B: ##EQU1##
The product is found by: ##EQU2## Thus P.sub.k are the partial product terms called the summands. There are mn summands, which are produced in parallel by a set of mn AND gates. For four bit values A and B, the expression above may be expanded into the partial products or summands set forth in Table 1.
TABLE 1 ______________________________________ A.sub.3 B.sub.0 A.sub.2 B.sub.0 A.sub.1 B.sub.0 A.sub.0 B.sub.0 A.sub.3 B.sub.1 A.sub.2 B.sub.1 A.sub.1 B.sub.1 A.sub.0 B.sub.1 A.sub.3 B.sub.2 A.sub.2 B.sub.2 A.sub.1 B.sub.2 A.sub.0 B.sub.2 A.sub.3 B.sub.3 A.sub.2 B.sub.3 A.sub.1 B.sub.3 A.sub.0 B.sub.3 P7 P6 P5 P4 P3 P2 P1 P0 ______________________________________
An n.times.n multiplier requires n(n-2) full adders, n half adders and n.sup.2 AND gates. The worst case delay associated with such a multiplier is (2n+1).tau..sub.g, where .tau..sub.g is the worst case adder delay.
FIGS. 1, 2 show parallel multiplier cell 10 for forming parallel multiplier array 30 to provide, for example, the partial products or summands of Table 1. The A.sub.i term of value input line 16 of parallel multiplier cell 10 is propagated vertically, through cell 10. The B.sub.j term of value input line 18 of parallel multiplier cell 10 propagates horizontally through cell 10. Incoming partial product term P.sub.i enters at the top left of parallel multiplier cell 10 by way of partial product input line 12. Incoming carry-in values enter at the top left of parallel multiplier cell 10 by way of carry-in line 14.
A bit-wise AND of A.sub.i on value input line 16 and B.sub.j on value input line 18 is performed in parallel multiplier cell 10 by AND gate 22. The output of AND gate 22 and the incoming partial product term P.sub.i of partial product input line 12 are applied to adder 20 or summer 20. The output sum value of adder 20 is passed to a diagonally adjacent parallel multiplier cell 10 in the next row and the next column of parallel multiplier array 30 by way of partial product output line 24 at the lower right of parallel multiplier cell 10. The carry-out term of adder 20 is passed to the next vertically adjacent cell below parallel multiplier cell 10 in parallel multiplier array 30 by way of carry-out line 26.
Parallel multiplier array 30 therefore is adapted to provide partial products, P0-P7, as set forth in Table 1. Thus parallel multiplier 30 is adapted to multiply two four-bit binary values. The partial product terms of the multiplication, P0-P7, are provided at parallel multiplier array 30 output lines 24. To perform the multiplication of input value A and input value B, the four bits of value A are applied to respective value input lines 16 of parallel multiplier array 30. The four bits of value B are applied to respective value input lines 18 of multiplier array 30. As show in FIG. 3, parallel multiplier array 30 may be redrawn as a square parallel multiplier array 30. A square parallel multiplier array 30 is the most convenient for implementation. Many other configurations for performing multiplication of binary values are also known in the art.